package ten.test_10_14;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class Solution {
    List<int[]> freq = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> sequence = new ArrayList<>();
    public int[][] combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if(freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                freq.get(size - 1)[1]++;
            }
        }
        dfs(0, target);
        Collections.sort(ans, (a, b) -> {
            if(a.size() != b.size()) {
                return a.size() - b.size();
            } else {
                for (int i = 0; i < a.size(); i++) {
                    if(!a.get(i).equals(b.get(i))) {
                        return a.get(i) - b.get(i);
                    }
            }
            }
            return 0;
        });
        return ans.stream().map(x -> x.stream().mapToInt(i->i).toArray()).toArray(int[][]::new);
    }
    private void dfs(int pos,int rest) {
        if(rest == 0) {
            Collections.sort(sequence);
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }
        dfs(pos + 1, rest);
        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; i++) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; i++) {
            sequence.remove(sequence.size() - 1);
        }
    }
    public int findMinDifference (String[] timePoints) {
        // write code here
        Arrays.sort(timePoints);
        int ans = Integer.MAX_VALUE;
        int t0Minutes = getMinutes(timePoints[0]);
        int preMinutes = t0Minutes;
        for (int i = 1; i < timePoints.length; ++i) {
            int minutes = getMinutes(timePoints[i]);
            ans = Math.min(ans, minutes - preMinutes);
            preMinutes = minutes;
        }
        ans = Math.min(ans, t0Minutes + 1440 - preMinutes);
        return ans;
    }
    public int getMinutes (String t) {
        return ((t.charAt(0) - '0')*10 + (t.charAt(1) - '0')) * 60 + (t.charAt(3) - '0') * 10 + (t.charAt(4) - '0');
    }
}
